Array of doubled pairs [Greedy]

Time: O(N+KLogK); Space: O(K); medium

Given an array of integers A with even length, return True if and only if it is possible to reorder it such that A[2 * i + 1] = 2 * A[2 * i] for every 0 <= i < len(A) / 2.

Example 1:

Input: A = [3,1,3,6]

Output: False

Example 2:

Input: A = [2,1,2,6]

Output: False

Example 3:

Input: A = [4,-2,2,-4]

Output: True

Explanation:

• We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].

Example 4:

Input: [1,2,4,16,8,4]

Output: False

Notes:

• 0 <= A.length <= 30000

• A.length is even

• -100000 <= A[i] <= 100000

1. Greedy

Intuition If x is currently the array element with the least absolute value, it must pair with 2*x, as there does not exist any other x/2 to pair with it.

Algorithm Let’s try to (virtually) “write” the final reordered array. Let’s check elements in order of absolute value. When we check an element x and it isn’t used, it must pair with 2*x. We will attempt to write x, 2x - if we can’t, then the answer is false. If we write everything, the answer is true.

To keep track of what we have not yet written, we will store it in a count.

import collections

class Solution1(object):
    def canReorderDoubled(self, A):
        """
        :type A: List[int]
        :rtype: bool
        """
        count = collections.Counter(A)
        for x in sorted(A, key = abs):
            if count[x] == 0: continue
            if count[2*x] == 0: return False
            count[x] -= 1
            count[2*x] -= 1

        return True

s = Solution1()
A = [3,1,3,6]
assert s.canReorderDoubled(A) == False
A = [2,1,2,6]
assert s.canReorderDoubled(A) == False
A = [4,-2,2,-4]
assert s.canReorderDoubled(A) == True
A = [1,2,4,16,8,4]
assert s.canReorderDoubled(A) == False

import collections

class Solution2(object):
    def canReorderDoubled(self, A):
        """
        :type A: List[int]
        :rtype: bool
        """
        count = collections.Counter(A)
        for x in sorted(count, key=abs):
            if count[x] > count[2*x]:
                return False
            count[2*x] -= count[x]
        return True

s = Solution2()
A = [3,1,3,6]
assert s.canReorderDoubled(A) == False
A = [2,1,2,6]
assert s.canReorderDoubled(A) == False
A = [4,-2,2,-4]
assert s.canReorderDoubled(A) == True
A = [1,2,4,16,8,4]
assert s.canReorderDoubled(A) == False

See also:

https://leetcode.com/problems/array-of-doubled-pairs